#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdint.h>
#include <windows.h>

// 大数结构体
typedef struct {
    uint32_t *digits;  // 数字数组，每个元素代表32位
    size_t length;     // 数组长度
    int sign;          // 符号（这里只处理正数）
} BigInt;

// 函数前置声明
BigInt* bigint_from_string(const char *str);
void bigint_free(BigInt *num);
int bigint_compare(const BigInt *a, const BigInt *b);
void bigint_mod(BigInt *a, const BigInt *b, BigInt *result);
void bigint_subtract(BigInt *a, const BigInt *b, BigInt *result);
void bigint_multiply_uint32(BigInt *a, uint32_t b, BigInt *result);
void bigint_divide_by_two(BigInt *num);
void bigint_pow_mod(BigInt *a, BigInt *b, BigInt *m, BigInt *result);

// 辅助函数：从字符串初始化大数
BigInt* bigint_from_string(const char *str) {
    size_t len = strlen(str);
    if (len == 0) return NULL;
    
    BigInt *num = (BigInt*)malloc(sizeof(BigInt));
    if (!num) return NULL;
    
    num->length = (len + 8) / 9;  // 每个uint32_t可以存储9位十进制数
    num->digits = (uint32_t*)calloc(num->length, sizeof(uint32_t));
    if (!num->digits) {
        free(num);
        return NULL;
    }
    
    num->sign = 1;  // 只处理正数
    
    for (size_t i = 0; i < len; ++i) {
        if (str[i] < '0' || str[i] > '9') {
            free(num->digits);
            free(num);
            return NULL;
        }
        
        // 大数乘以10
        uint64_t carry = 0;
        for (size_t j = 0; j < num->length; ++j) {
            carry += (uint64_t)num->digits[j] * 10;
            num->digits[j] = (uint32_t)(carry % 1000000000);
            carry /= 1000000000;
        }
        
        // 加上当前数字
        carry = str[i] - '0';
        for (size_t j = 0; carry && j < num->length; ++j) {
            carry += num->digits[j];
            num->digits[j] = (uint32_t)(carry % 1000000000);
            carry /= 1000000000;
        }
    }
    
    return num;
}

// 辅助函数：释放大数
void bigint_free(BigInt *num) {
    if (num) {
        if (num->digits) free(num->digits);
        free(num);
    }
}

// 辅助函数：比较两个大数
int bigint_compare(const BigInt *a, const BigInt *b) {
    if (a->length > b->length) return 1;
    if (a->length < b->length) return -1;
    
    for (size_t i = a->length; i-- > 0; ) {
        if (a->digits[i] > b->digits[i]) return 1;
        if (a->digits[i] < b->digits[i]) return -1;
    }
    
    return 0;
}

// 辅助函数：大数取模
void bigint_mod(BigInt *a, const BigInt *b, BigInt *result) {
    // 简化实现：这里假设b是小整数（对于Miller-Rabin测试足够）
    // 实际完整实现需要完整的大数除法，这里为简化代码省略
    
    // 这里我们假设b是小整数（小于2^32）
    if (b->length != 1) {
        // 简化处理，实际应用中需要完整实现
        result->digits[0] = 0;
        return;
    }
    
    uint64_t divisor = b->digits[0];
    uint64_t remainder = 0;
    
    for (size_t i = a->length; i-- > 0; ) {
        remainder = (remainder * 1000000000 + a->digits[i]) % divisor;
    }
    
    result->digits[0] = (uint32_t)remainder;
    result->length = 1;
}

// 辅助函数：大数减法
void bigint_subtract(BigInt *a, const BigInt *b, BigInt *result) {
    // 简化实现：假设a >= b
    uint64_t borrow = 0;
    
    for (size_t i = 0; i < a->length; ++i) {
        uint64_t subtrahend = (i < b->length) ? b->digits[i] : 0;
        uint64_t diff = (uint64_t)a->digits[i] - subtrahend - borrow;
        
        borrow = (diff > a->digits[i]) ? 1 : 0;
        result->digits[i] = (uint32_t)(diff & 0xFFFFFFFF);
    }
    
    result->length = a->length;
    while (result->length > 1 && result->digits[result->length - 1] == 0) {
        result->length--;
    }
}

// 辅助函数：大数乘以小整数
void bigint_multiply_uint32(BigInt *a, uint32_t b, BigInt *result) {
    uint64_t carry = 0;
    
    for (size_t i = 0; i < a->length; ++i) {
        carry += (uint64_t)a->digits[i] * b;
        result->digits[i] = (uint32_t)(carry % 1000000000);
        carry /= 1000000000;
    }
    
    if (carry) {
        result->digits[a->length] = (uint32_t)carry;
        result->length = a->length + 1;
    } else {
        result->length = a->length;
    }
}

// 辅助函数：大数除以2
void bigint_divide_by_two(BigInt *num) {
    uint64_t remainder = 0;
    
    for (size_t i = num->length; i-- > 0; ) {
        uint64_t value = (remainder * 1000000000) + num->digits[i];
        num->digits[i] = (uint32_t)(value / 2);
        remainder = value % 2;
    }
    
    while (num->length > 1 && num->digits[num->length - 1] == 0) {
        num->length--;
    }
}

// 辅助函数：大数取幂模（a^b mod m）
void bigint_pow_mod(BigInt *a, BigInt *b, BigInt *m, BigInt *result) {
    BigInt *base = bigint_from_string("1");
    BigInt *exp = bigint_from_string("0");
    BigInt *temp = bigint_from_string("0");
    BigInt *one = bigint_from_string("1");
    BigInt *two = bigint_from_string("2");
    
    // 复制a到result
    memcpy(result->digits, a->digits, a->length * sizeof(uint32_t));
    result->length = a->length;
    
    // 复制b到exp
    memcpy(exp->digits, b->digits, b->length * sizeof(uint32_t));
    exp->length = b->length;
    
    // 初始化base为1
    base->digits[0] = 1;
    base->length = 1;
    
    while (bigint_compare(exp, one) >= 0) {
        bigint_mod(exp, two, temp);
        if (temp->digits[0] == 1) {  // 如果指数是奇数
            // base = (base * result) % m
            bigint_multiply_uint32(base, result->digits[0], temp);
            bigint_mod(temp, m, base);
        }
        
        // result = (result * result) % m
        bigint_multiply_uint32(result, result->digits[0], temp);
        bigint_mod(temp, m, result);
        
        // exp = exp / 2
        bigint_divide_by_two(exp);
    }
    
    // 最终结果在base中
    memcpy(result->digits, base->digits, base->length * sizeof(uint32_t));
    result->length = base->length;
    
    bigint_free(base);
    bigint_free(exp);
    bigint_free(temp);
    bigint_free(one);
    bigint_free(two);
}

// Miller-Rabin素性测试
int miller_rabin_test(BigInt *n, int iterations) {
    if (n->length == 1 && n->digits[0] < 2) return 0;
    if (n->length == 1 && (n->digits[0] == 2 || n->digits[0] == 3)) return 1;
    
    BigInt *n_minus_1 = bigint_from_string("0");
    BigInt *d = bigint_from_string("0");
    BigInt *a = bigint_from_string("0");
    BigInt *x = bigint_from_string("0");
    BigInt *two = bigint_from_string("2");
    BigInt *one = bigint_from_string("1");
    
    // n-1 = d * 2^s
    bigint_subtract(n, one, n_minus_1);
    memcpy(d->digits, n_minus_1->digits, n_minus_1->length * sizeof(uint32_t));
    d->length = n_minus_1->length;
    
    int s = 0;
    while (d->digits[0] % 2 == 0) {
        bigint_divide_by_two(d);
        s++;
    }
    
    // 测试迭代
    for (int i = 0; i < iterations; i++) {
        // 选择随机a ∈ [2, n-2]
        // 简化：这里使用固定的小质数作为基数
        static const uint32_t bases[] = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
        if (i < sizeof(bases)/sizeof(bases[0])) {
            a->digits[0] = bases[i];
            a->length = 1;
        } else {
            // 随机选择a，简化处理
            a->digits[0] = 2 + (rand() % (n->digits[0] - 3));
            a->length = 1;
        }
        
        if (bigint_compare(a, n_minus_1) >= 0) {
            a->digits[0] = n_minus_1->digits[0] - 1;
        }
        
        // x = a^d mod n
        bigint_pow_mod(a, d, n, x);
        
        if (bigint_compare(x, one) == 0 || bigint_compare(x, n_minus_1) == 0) {
            continue;
        }
        
        int is_composite = 1;
        for (int j = 0; j < s - 1; j++) {
            // x = x^2 mod n
            bigint_multiply_uint32(x, x->digits[0], x);
            bigint_mod(x, n, x);
            
            if (bigint_compare(x, one) == 0) {
                bigint_free(n_minus_1);
                bigint_free(d);
                bigint_free(a);
                bigint_free(x);
                bigint_free(two);
                bigint_free(one);
                return 0;
            }
            
            if (bigint_compare(x, n_minus_1) == 0) {
                is_composite = 0;
                break;
            }
        }
        
        if (is_composite) {
            bigint_free(n_minus_1);
            bigint_free(d);
            bigint_free(a);
            bigint_free(x);
            bigint_free(two);
            bigint_free(one);
            return 0;
        }
    }
    
    bigint_free(n_minus_1);
    bigint_free(d);
    bigint_free(a);
    bigint_free(x);
    bigint_free(two);
    bigint_free(one);
    
    return 1;
}

// 导出函数：判断是否为质数
__declspec(dllexport) int is_prime(const char *number_str) {
    BigInt *num = bigint_from_string(number_str);
    if (!num) return -1;  // 无效输入
    
    // 简单情况处理
    if (num->length == 1) {
        uint32_t n = num->digits[0];
        bigint_free(num);
        
        if (n < 2) return 0;
        if (n == 2 || n == 3) return 1;
        if (n % 2 == 0) return 0;
        
        // 对小整数使用确定性测试
        for (uint32_t i = 3; i * i <= n; i += 2) {
            if (n % i == 0) return 0;
        }
        return 1;
    }
    
    // 检查偶数
    if (num->digits[0] % 2 == 0) {
        bigint_free(num);
        return 0;
    }
    
    // 对大数使用Miller-Rabin测试
    int result = miller_rabin_test(num, 10);  // 10次迭代
    
    bigint_free(num);
    return result;
}

// DLL入口点
BOOL APIENTRY DllMain(HMODULE hModule, DWORD ul_reason_for_call, LPVOID lpReserved) {
    switch (ul_reason_for_call) {
        case DLL_PROCESS_ATTACH:
        case DLL_THREAD_ATTACH:
        case DLL_THREAD_DETACH:
        case DLL_PROCESS_DETACH:
            break;
    }
    return TRUE;
}